package main

/*
给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/ga4o2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

import "fmt"

func findTargetSumWays(nums []int, target int) int {
	var cnt int
	dfsSearch(nums, 0, target, 0, &cnt)
	return cnt
}

func dfsSearch(nums []int, idx int, target int, tmpRes int, cnt *int) {
	if idx >= len(nums) {
		if tmpRes == target {
			*cnt++
		}
		return
	}
	// 遍历子节点，子节点就是+next 和-next
	dfsSearch(nums, idx+1, target, tmpRes+nums[idx], cnt)
	dfsSearch(nums, idx+1, target, tmpRes-nums[idx], cnt)
}

func main() {
	nums := []int{1, 1, 1, 1, 1}
	target := 3
	fmt.Println(findTargetSumWays(nums, target))
}
